//方法一
function quickSort(arr) {
    if (arr.length === 0) {
        return []
    }
    let flag = arr[0];
    let leftArr = [];
    let rightArr = [];
    arr.slice(1).forEach(item => {
        if(item<arr[0]){
            leftArr.push(item)
        }else{
            rightArr.push(item)
        }
    });
    return quickSort(leftArr).concat([flag], quickSort(rightArr))
}

const arr = [5, 2,9, 3, 8, 6, 2,4]
//console.log(quickSort(arr))

//方式2(原地算法)
function QSort(arr){
    if(arr.length<=1){
        return arr
    }
    let priovt=arr[0]
    let i=1
    let j=arr.length-1
    while(i<j){
        while(i<j&&arr[j]>=priovt){
            j--
        }
        while(i<j&&arr[i]<priovt){
            i++
        }
        let temp=arr[j]
        arr[j]=arr[i]
        arr[i]=temp
    }
    let left=arr.slice(1,i+1)
    let right=arr.slice(j+1)
    return [...QSort(left),priovt,...QSort(right)]
}
console.log(QSort(arr))



